package leetCode.competition;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class Code_208 {
    @Test
    public void test() {
        Code_208 code208 = new Code_208();
        code208.insert("fghjdfgjdsbgjkbvjdsfhgvbdsjrhguhjsdhjfbhds");
        System.out.println(code208.search("fghjdfgjdsbgjkbvjdsfhgvbdsjrhguhjsdhjfbhds"));
    }

    private char value; //存储当前的字符
    private List<Code_208> sons; //儿子节点
    private String storage; //存储的字符串

    public Code_208() {
        sons = new ArrayList<Code_208>();
        storage = "";
    }

    public void insert(String word) {
        Code_208 tmpNode = this;
        boolean flag;
        int count = 0;
        for (int i = 0; i < word.length(); i++) {
            flag = true;
            for (int j = 0; j < tmpNode.sons.size(); j++) {
                if (tmpNode.sons.get(j).value == word.charAt(i)) {
                    flag = false;
                    tmpNode = tmpNode.sons.get(j);
                    count++;
                    break;
                }
            }
            if (flag) break;
        }
        for (int i = count; i < word.length(); i++) {
            Code_208 tmp = new Code_208();
            tmp.value = word.charAt(i);
            tmpNode.sons.add(tmp);
            tmpNode = tmpNode.sons.get(tmpNode.sons.size() - 1);
        }
        tmpNode.storage = word;
    }

    public boolean search(String word) {
        Code_208 tmpNode = this;
        boolean flag;
        for (int i = 0; i < word.length(); i++) {
            flag = true;
            for (int j = 0; j < tmpNode.sons.size(); j++) {
                if (word.charAt(i) == tmpNode.sons.get(j).value) {
                    flag = false;
                    tmpNode = tmpNode.sons.get(j);
                    break;
                }
            }
            if (flag) break;
        }
        return tmpNode.storage.equals(word);
    }

    public boolean startsWith(String prefix) {
        Code_208 tmpNode = this;
        boolean flag;
        int count = 0;
        for (int i = 0; i < prefix.length(); i++) {
            flag = true;
            for (int j = 0; j < tmpNode.sons.size(); j++) {
                if (prefix.charAt(i) == tmpNode.sons.get(j).value) {
                    flag = false;
                    tmpNode = tmpNode.sons.get(j);
                    count++;
                }
            }
            if (flag) break;
        }
        return count == prefix.length();
    }
}
